package day2_linkedlist.leetcode;

/**
 * @Author: yuisama
 * @Date: 2021/8/29 17:41
 * @Description:删除链表中所有节点值为val的元素
 * 给你一个链表的头节点 head 和一个整数 val ，
 * 请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
 */
public class Num203_remove_list_node {
    // 虚拟头结点法
//    public ListNode removeElements(ListNode head, int val) {
//        // 设置虚拟头结点
//        ListNode dummyHead = new ListNode(-1,head);
//        ListNode prev = dummyHead;
//        while (prev.next != null) {
//            // prev恰好是待删除节点的前驱节点
//            if (prev.next.val == val) {
//                prev.next = prev.next.next;
//            }else {
//                prev = prev.next;
//            }
//        }
//        return dummyHead.next;
//    }

    // 常规做法
//    public ListNode removeElements(ListNode head, int val) {
//        // 判断头结点需要删除
//        while (head != null && head.val == val) {
//            head = head.next;
//        }
//        // 判断链表为空
//        if(head == null)
//            return null;
//        ListNode prev = head;
//        while (prev.next != null) {
//            if (prev.next.val == val) {
//                prev.next = prev.next.next;
//            }else {
//                prev = prev.next;
//            }
//        }
//        return head;
//    }

    // 递归法
    // 此函数的语义为:删除给定链表中值为val的节点
    public ListNode removeElements(ListNode head, int val) {
        // 终止条件，若链表为空，此时不需要再删除
        if (head == null)
            return null;
        head.next = removeElements(head.next,val);
        if (head.val == val)
            return head.next;
        return head;
    }
}
